#define _CRT_SECURE_NO_WARNINGS 1

//P2036[COCI2008 - 2009#2] PERKET
//https://www.luogu.com.cn/problem/P2036

//#include<iostream>
//#include<algorithm>
//
//using namespace std;
//
//int n;
//const int N = 15;
//int Bitt[N];	//苦
//int Acid[N];	//酸
//int res=1e9;		//差值
//int st[N];		//记录数组——是否使用 0未选择，1使用，2不用
//
//
//void dfs(int x)
//{
//	if (x > n)
//	{
//		bool has_tl = false;	//判断该方案至少选没选1个
//		int sum = 0;
//		int cal = 1;
//		for (int i = 1; i <= n; i++)
//		{
//			//易错点：必须要选了才能计算酸苦度
//			if (st[i] == 1)
//			{
//				has_tl = true;
//				sum = sum+Bitt[i];
//				cal *= Acid[i];
//			}
//		}
//		if (has_tl)			//该方案至少选了1个
//			res = min(res, abs(sum - cal));
//		return;
//	}
//	//不用
//	st[x] = 2;
//	dfs(x + 1);
//	st[x] = 0;
//
//	//用
//	st[x] = 1;
//	
//	dfs(x + 1);
//	st[x] = 0;
//}
//
//int main()
//{
//	scanf("%d", &n);
//	for (int i = 1; i <= n; i++)
//	{
//		scanf("%d%d", &Acid[i], &Bitt[i]);
//	}
//	dfs(1);
//	cout << res << endl;
//
//	return 0;
//}

//https://www.luogu.com.cn/problem/P1683
//P1683 入门

//#include<iostream>
//
//using namespace std;
//
//int n, m;//n行m列
//const int N = 30;
//bool st[N][N];
//char g[N][N];
//int dx[] = { -1,0,1,0 };
//int dy[] = { 0,1,0,-1 };
//int res;
//
//void dfs(int x, int y)
//{
//	for (int i = 0; i < 4; i++)
//	{
//		int a = x + dx[i], b = y + dy[i];
//		if (a < 0 || a >= n || b < 0 || b >= m)
//			continue;
//		if (g[a][b] != '.')
//			continue;
//		if (st[a][b])
//			continue;
//
//
//		st[a][b] = true;
//		res++;
//		dfs(a, b);
//		//为什么不回溯？4个方向都走了，所以不用回去重新走?防止重复计数?
//	}
//}
//
//int main()
//{
//	scanf("%d%d", &m, &n);
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%s", g[i]);//数组名就是数组首元素地址
//	}
//
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < m; j++)
//		{
//			if (g[i][j] == '@')
//			{
//				st[i][j] = true;
//				dfs(i, j);
//			}
//		}
//	}
//	res++;
//	cout << res << endl;
//	return 0;
//}


//https://www.luogu.com.cn/problem/P1596
//P1596[USACO10OCT]Lake Counting S 洪水淹没问题

//#include<iostream>
//
//using namespace std;
//
//int n, m;
//const int N = 110;
//char g[N][N];
//bool st[N][N];
//int res = 0;
//int dx[] = { 1,1,1,0,0,-1,-1,-1 };
//int dy[] = { 1,0,-1,1,-1,1,0,-1 };
//
//
//
//void dfs(int x, int y)
//{
//	for (int i = 0; i < 8; i++)
//	{
//		int a = x + dx[i];
//		int b = y + dy[i];
//
//		if (a < 0 || a >= n || b < 0 || b >= m)
//			continue;
//		if (g[a][b] != 'W')		//不是water
//			continue;
//		if (st[a][b])	//走过了
//			continue;
//
//		st[a][b] = true;
//		dfs(a, b);
//	}
//}
//
//int main()
//{
//	scanf("%d%d", &n, &m);
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%s", g[i]);
//	}
//
//
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < m; j++)
//		{
//			if (g[i][j] == 'W' && !st[i][j])
//			{
//				dfs(i, j);
//				res++;
//			}
//		}
//	}
//	cout << res << endl;
//	return 0;
//}

//https://www.acwing.com/problem/content/description/1116/
//1114. 棋盘问题

#include<iostream>

//using namespace std;
//
//const int N = 15;
//int n, k;
//char board[N][N];
//bool flag[N];
//int res = 0;
//
////x表示当前在哪一行，cnt表示棋子数
//void dfs(int x, int cnt)
//{
//	if (cnt == k)
//	{
//		res++;
//		return;
//	}
//	
//	if (x >= n)
//	{
//		return;
//	}
//
//	//枚举
//	for (int i = 0; i < n; i++)
//	{
//		if ((!flag[i]) && (board[x][i] == '#'))
//		{
//			flag[i] = true;
//			dfs(x + 1, cnt + 1);
//			flag[i] = false;
//		}
//	}
//
//	dfs(x + 1, cnt);
//}
//
//int main()
//{
//	while (cin >> n >> k, n>0 && k>0)
//	{
//		for (int i = 0; i < n; i++)
//		{
//			scanf("%s", board[i]);
//		}
//		res = 0;
//		dfs(0, 0);
//		cout << res << endl;
//	}
//	return 0;
//}


//https://www.luogu.com.cn/problem/P1025
//P1025[NOIP2001 提高组] 数的划分

//#include<iostream>
//
//using namespace std;
//
//
//const int N = 10;
//int n, k;
//int arr[N];
//int res = 0;
//
//
////x表示位置,state表示从state数值开始往后选数，（state———n）
//void dfs(int x,int state,int sum)
//{
//	//if (sum > n)
//	//	return;
//
//	//if (x > k)
//	//{
//	//	if (sum == n)
//	//	{
//	//		//for (int i = 1; i <= k; i++)
//	//		//{
//	//		//	cout << arr[i] << ' ';
//	//		//}
//	//		//cout << endl;
//	//		res++;
//	//	}
//	//	//for (int i = 1; i <= k; i++)
//	//	//{
//	//	//	cout << arr[i] << ' ';
//	//	//}
//	//	//cout << endl;
//	//	return;
//	//}
//
//	//for (int i = state; i <= n; i++)
//	//{
//	//	arr[x] = i;
//	//	dfs(x + 1,i,sum+i);
//	//	arr[x] = 0;
//	//}
//
////优化剪枝操作，不需sum>n了，判断当前后面的数+现在的和≤n，否则超出不需进行。
//
//	if (x > k)
//	{
//		if (sum == n)
//		{
//			res++;
//		}
//		return;
//	}
//
//	for (int i = state; sum+i*(k-x+1) <= n; i++)
//	{
//		arr[x] = i;
//		dfs(x + 1, i, sum + i);
//		arr[x] = 0;
//	}
//}
//
//int main()
//{
//	cin >> n >> k;
//	dfs(1,1,0);
//	cout << res << endl;
//	return 0;
//}



//https://www.luogu.com.cn/problem/P1019
//P1019[NOIP2000 提高组] 单词接龙


